package com.copa.l1356;

import java.util.*;

/**
 * @author copa
 * @createDate 2022-09-05 16:53
 * @function 暴力法
 */
public class Test1 {

    public int[] sortByBits(int[] arr) {
        // 用来存储 <1的个数，对应arr符合数的集合>
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
        Arrays.sort(arr);
        for (int i = 0; i < arr.length; i++) {
            int bitCount = Integer.bitCount(arr[i]);
            if (map.get(bitCount) == null) {
                map.put(bitCount, new ArrayList<>());
            }
            map.get(bitCount).add(arr[i]);
        }
        // 因为key是无序的，所以需要弄成有序
        Integer[] array = map.keySet().toArray(new Integer[map.size()]);
        Arrays.sort(array);
        int[] result = new int[arr.length];

        // 有序双重遍历
        int temp = 0;
        for (Integer count : array) {
            for (Integer num : map.get(count)) {
                result[temp++] = num;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr = {0,1,2,3,4,5,6,7,8};
        int[] result = new Test1().sortByBits(arr);
        for (int i : result) {
            System.out.print(i + "\t");
        }

    }
}
